package Ch_2_5_Applications;

import edu.princeton.cs.algs4.*;

public class Practise_2_5_30 {
    public static int[][] matrix(int N, int M) {
        int[][] matrix = new int[N][];
        for (int i = 0; i < N; i++) {
            matrix[i] = new int[M];
            for (int j = 0; j < M; j++)
                matrix[i][j] = StdRandom.uniform(100);
        }
        return matrix;
    }
    public static void printMatrix(int[][] a) {
        StdOut.println();
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++)
                StdOut.printf(" %4d ", a[i][j]);
            StdOut.println("\n");
        }   
    }
    public static void shellColumn(int[][] a, int k) {
        int N = a.length, h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                int t = a[i][k], j;
                for (j = i - h; j >= 0 && t < a[j][k]; j -= h)
                    a[j + h][k] = a[j][k];
                a[j + h][k] = t;
            }
            h /= 3;
        }
    }
    public static void shellRow(int[][] a, int k) {
        int N = a[0].length, h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                int t = a[k][i], j;
                for (j = i - h; j >= 0 && t < a[k][j]; j -= h)
                    a[k][j + h] = a[k][j];
                a[k][j + h] = t;
            }
            h /= 3;
        }
    }
    public static void main(String[] args) {
        int rows = 12, columns = 14;
        int[][] a = matrix(rows, columns);
        StdOut.println("================================= 排序前 ======================================  ");
        printMatrix(a);
        for (int i = 0; i < columns; i++)
            shellColumn(a, i);
        StdOut.println("=================================  对所有列排序 =================================  ");
        printMatrix(a);
        for (int i = 0; i < rows; i++)
            shellRow(a, i);
        StdOut.println("=================================  对所有行排序 =================================  ");
        printMatrix(a);
    }
    // output
    /*
     * ================================= 排序前 ======================================  

       90    35    56    42    44    79    10    13    15    76    58    14    88     2 
    
       32    73    79    35    39    76    59    84    60    55    16    52    82     3 
    
        0    18    35    59     3    69    17    37    47    82    15    76     4    14 
    
       77    10    35    45    64    40    46    11    55    53    48    83     6     9 
    
       91    10    96    24    74    17    40    49    65    67    38    73    39    86 
    
       76    47    42    89     4     9    72    52    16    16    31     0    41    82 
    
       44     2    26    38    81    90    77    14    30    97    60     1    90    60 
    
       78    51    40    64    45    94    65     4    76     2    26    18    81    49 
    
       34    95    56    38    18    16    80    53    78    89    44    64    15    22 
    
       55    12    76    21    65    94    85     0    77    57    74    96    67    34 
    
       34    31    79    56    95     2    61    62    95    95    12     6    50    43 
    
       61    59    47    19    89    19    13     5     4    11    66    14     1    25 
    
    =================================  对所有列排序 =================================  
    
        0     2    26    19     3     2    10     0     4     2    12     0     1     2 
    
       32    10    35    21     4     9    13     4    15    11    15     1     4     3 
    
       34    10    35    24    18    16    17     5    16    16    16     6     6     9 
    
       34    12    40    35    39    17    40    11    30    53    26    14    15    14 
    
       44    18    42    38    44    19    46    13    47    55    31    14    39    22 
    
       55    31    47    38    45    40    59    14    55    57    38    18    41    25 
    
       61    35    56    42    64    69    61    37    60    67    44    52    50    34 
    
       76    47    56    45    65    76    65    49    65    76    48    64    67    43 
    
       77    51    76    56    74    79    72    52    76    82    58    73    81    49 
    
       78    59    79    59    81    90    77    53    77    89    60    76    82    60 
    
       90    73    79    64    89    94    80    62    78    95    66    83    88    82 
    
       91    95    96    89    95    94    85    84    95    97    74    96    90    86 
    
    =================================  对所有行排序 =================================  
    
        0     0     0     1     2     2     2     2     3     4    10    12    19    26 
    
        1     3     4     4     4     9    10    11    13    15    15    21    32    35 
    
        5     6     6     9    10    16    16    16    16    17    18    24    34    35 
    
       11    12    14    14    15    17    26    30    34    35    39    40    40    53 
    
       13    14    18    19    22    31    38    39    42    44    44    46    47    55 
    
       14    18    25    31    38    38    40    41    45    47    55    55    57    59 
    
       34    35    37    42    44    50    52    56    60    61    61    64    67    69 
    
       43    45    47    48    49    56    64    65    65    65    67    76    76    76 
    
       49    51    52    56    58    72    73    74    76    76    77    79    81    82 
    
       53    59    59    60    60    76    77    77    78    79    81    82    89    90 
    
       62    64    66    73    78    79    80    82    83    88    89    90    94    95 
    
       74    84    85    86    89    90    91    94    95    95    95    96    96    97 
     */
}
